\documentclass[twocolumn,11pt]{article}
\usepackage{usenix}
\usepackage{url}
\usepackage{graphics}

\usepackage{hyperref}


% -------------------------------------------------------------------------
%                                   Title
% -------------------------------------------------------------------------

\title{\bf \textsf{Smarter Swapping to Flash}}

\author{Sean Bauer, Devon Harris, Brett Panosh\
\\
       {\em \normalsize Computer Sciences Department}\\
       {\em \normalsize University of Wisconsin, Madison, WI USA}\\
       {\tt \normalsize \{sbauer,devon,brett\} @cs.wisc.edu}}

\begin{document}
 \date{}
\raggedbottom

\maketitle


\pagenumbering{arabic}
\pagestyle{plain}
%%\pagestyle{empty}


\setlength{\footskip}{25pt}
% -------------------------------------------------------------------------
%                               Introduction
% -------------------------------------------------------------------------
\begin{abstract}
\small
\noindent Flash-based storage is becoming increasingly popular given its consistently, decreasing cost.  Our research is based on the idea that optimizing the Linux kernel for flash can increase operating system performance and the life of flash-based storage.  Our first step was to port a system that has already been proven to do these things, FlashVM, to the newest version of the Linux kernel.  Our second step was to enhance the current prefetching system to take advantage of flash.  Since flash reads are much faster than disk’s, we should be able to pull in more pages and possibly more accurate pages as well.  The FlashVM system alone has decreased the number of writes to flash up to 5.2\%.  We hope to see a further increase once we finish the prefetching system.

\end{abstract}

\begin{sloppypar}
\section{Introduction}
\label{sec:Introduction}

\noindent The Raspberry Pi is a new, single-board computer the size of a credit card.  The default operating system of the Pi is known as the Raspian OS, which is a Pi-optimized version of Debian Linux.  The Pi does not make use of a hard drive or solid-state drive for long-term storage but instead uses an SD card.  The current version of the Raspian OS uses the Linux kernel version 3.2.27, and we believe that the kernel can be optimized to take advantage of the flash memory system, specifically through enhancing the swapping mechanism.

This paper presents performance enhancements made to the Linux kernel to benefit the Raspberry Pi by taking advantage of the Pi’s use of an SD card for long-term storage.  We strongly believe that this project is worthwhile due to the ever-increasing use of flash-based storage, especially when coupling this fact with the steadily decreasing prices of flash memory.  Aside from cost, flash memory has several advantages over disk including faster seek times and lower energy consumption.  That being said, flash does have a few disadvantages compared to disk.  “Flash is organized in pages typically of size 2K or 4K, which are read and written as a unit.” [cite]  In addition, flash accesses blocks rather than specific bytes or pages, where a block is typically 128 KB (64 or 32 pages).  So writing a byte of data translates to reading a full 128 KB block, changing the byte, and rewriting back the new block.  Essentially, random writes can be considerably expensive in terms of speed since it has to write a full block on every write rather than just a byte or page.  In addition, flash experiences memory wear, meaning that each flash device has a finite number of writes that can be performed on each block.  With this knowledge in mind, the Linux kernel can be optimized in two general situations.  First, the kernel can be modified to take advantage of flash’s relatively fast reads.  Second, the kernel can be modified to decrease the number of writes in order to avoid the slowness of writing and to promote the life of the flash device.

We began by porting code written by Mohit Saxena and Michael Swift for their FlashVM paper.  This code took advantage of several key factors of flash memory.  In response to the low seek time of flash, FlashVM prefetches more useful pages by using stride prefetching to minimize unwanted pages.  This reduces page faults and improves application execution time.  To combat memory wear, FlashVM employs zero-page sharing to avoid writing empty pages and page sampling to probabilistically skip over dirty pages in order to prioritize the replacement of clean pages.  These techniques reduce flash writes, thus improving the lifespan of the flash device.  The FlashVM code is written for the Linux 2.6 kernel, but we had to modify it to work with the more recent 3.2 kernel, which is the default kernel version for the Raspian OS.  After porting the code to the Pi, we immediately noticed a 5.2\% decrease in the amount of writes after a few tests.  

The remainder of the paper is structured as follows.  Section 2 presents our motivation for pursuing kernel enhancements for flash-based storage.  Section 3 introduces our overall design choices, details specific kernel changes made, and describes the challenges we faced.  Section 4 evaluates the optimized kernel through several experiments.  The paper finishes with Section 5 describing related work and Section 6 concluding our results.


% -------------------------------------------------------------------------
%                               Methodology
% -------------------------------------------------------------------------


\section{Motivation}
\label{sec:motivation}

\noindent Our interest in flash memory stems from its low cost, performance characteristics, and potential to become a dominant type of storage.  With the rise in popularity of flash storage, it makes sense to modify a popular kernel such as the Linux kernel to support enhancements for flash-based storage.  If significant performance gains can be realized then perhaps flash would increase in popularity even more rapidly.  In addition, due to the extremely low cost of the Raspberry Pi, we believe the Pi could become a fairly popular computer in the upcoming years.  That being said, our changes should work for any Linux distribution, but they will likely be best on the Raspian OS.

\begin{table}[t!!]
\small
\centering
\scalebox{0.6}{%
\begin{tabular}{|l|l|l|l|l|l|}
\hline
{\bf Device} & {\bf Random RD} & {\bf Seq RD} & {Random WR} & {Seq WR} & {Price(\$)/GB}  \\
\hline \hline
DRAM & 0.05 & 0.05 & 0.05 & 0.05 & \$15  \\
\hline
Flash & 100 & 85 & 2000 & 200-500 & \$3   \\
\hline
Disk & 5000 & 500 & 5000 & 500 & \$0.3  \\
\hline
\hline
\end{tabular} 
}
\caption{\small {\bf Comparison of storage mediums} Tradeoffs between DRAM, flash, and magnetic disk. Note: Estimated latencies are in microseconds.}
\label{table:devicecompare}
\end{table}

Table ~\ref{table:devicecompare} illustrates that while flash is more expensive than disk, by approximately 10 times, significant performance gains up to orders of magnitude faster can be realized through flash.  Also of importance, flash’s power consumption is significantly lower than disk.  Perhaps if flash’s cost continues to decrease it could best disks in both performance and cost.

\section{Design \& Implementation}
\label{sec:designimp}

\subsection{Goals}
\begin{enumerate}
\item {\em Performance} One of our primary goals in modifying the Linux memory system was to enable the Raspberry Pi to take full advantage of the improved characteristics of Flash memory. Specifically, we seek to leverage the fast random reads into a reduced number of page-faults by improving the prefetching mechanisms in the Linux kernel.
\item {\em Reliability} While flash has many advantages over disk, it also suffers from wear-out.  The existing Linux kernel takes no steps to limit writes to its swap device; we attempt to reduce this number of page writes using zero-page sharing and preferring to evict clean pages.
\end{enumerate}


\subsection{Implementation}
The changes to the Linux kernel affect several areas of the memory subsystem.

\subsubsection{Page Write-Back \& Scanning}
The Linux VM system regularly tries to reclaim memory to prepare for future memory demands. Page pre-cleaning is where the page-out daemon kswapd runs occasionally to swap out 32 pages from the inactive page list.  Since flash has a significantly higher write bandwidth than disk, an opportunity exists to pre-clean more aggressively, without harming other IO traffic.  So, we investigated the effects of pre-cleaning more pages each time kswapd is run.  

However, the rate at which Linux tries to write-back pages to the swap device must not exceed the bandwidth of said device.  Linux throttles write-backs via a {\em congestion\_wait} on the order of 10 - 100 milliseconds. This timeout is appropriate for disk, but was adjusted in our changes to better align with flash’s performance.  Writes to a full erase block on flash take 1 - 2 milliseconds, so our flash-based kernel only waits 1 millisecond.  As one can see, it is a simple change in code:
\begin{verbatim}
congestion_wait(WRITE, HZ/HZ);
//congestion_wait(WRITE, HZ/50);
\end{verbatim}
Without adjusting this timeout, the kernel would not be fully utilizing the increased speed and bandwidth of flash.


\subsubsection{Page Fault Pre-fetching}
To amortize the seek cost of disk, operating systems prefetch a contiguous region of pages from disk on each page fault.  In Linux, {\em swapin\_readahead} will prefetch up to 8 pages, but this region is limited by free or bad pages.  However, this mechanism only succeeds if page requests exhibit good spatial locality.

On flash, fast random reads allow us to improve the existing prefetching.  First, the kernel can skip over free/bad pages when choosing which pages to prefetch in order to grab a full set of pages each page fault.  Additionally, fast random reads enable more sophisticated methods than the simple spatial approach.  Consequently, we have included stride prefetching, which tracks offsets between page fault accesses and prefetches new pages along those strides.  This change is manifested within the {\em swapin\_readahead} function.
 
\begin{verbatim}
page = read_swap_cache_async(
	swp_entry(swp_type(entry), 
	offset[tmp_offset]), 
	gfp_mask, vma, addr);
\end{verbatim}

Prior to our addition, offset was simply a value or range of pages to grab. Now it is an array that holds specific pages to prefetch. The key idea here is to maximize the accuracy of prefetched pages or to minimize pollution (prefetched pages that end up not being used before being swapped out).

We are in the process of implementing adaptive prefetching.  The tradeoff is simple - prefetching more pages increases the average page fault latency, which hinders performance.  But, if those pages are later used (called a prefetch hit), then we have avoided a page fault altogether.

\begin{verbatim}
struct page {
   ...
   short isPrefetched;
}
\end{verbatim}

Our basic idea was to increase the number of pages being prefetched if our average prefetch accuracy is above a certain threshold.  Each program has different memory patterns that we would like the kernel prefetcher to adapt to.  On programs with predictable paging demands, the prefetcher should be more aggressive; on unpredictable loads, the prefetcher won’t be very accurate, and so should avoid increasing the average page fault latency.

\subsubsection{Page Sampling}
To improve the expected reliability of flash-based swapping systems, we also strove to reduce the number of writes to flash in an attempt to extend its lifetime.  As mentioned earlier, Linux reclaims pages in approximately an LRU order.  When re-claiming a clean page, the page is simply added to the free list, while a dirty page must be written back.  We experimented with skipping dirty pages to prioritize the reclamation of clean pages and lessen the number of writes to flash.
	
Similar to prefetching, the optimal parameters here depend largely on the memory patterns of each application.  If a program uses read-mostly data, then there will likely be many clean pages that can be reclaimed.  But, skipping dirty pages may have a negative effect on write-mostly workloads because we could be evicting clean pages that are needed soon, resulting in increased page faults.  To address this variation, we again use an adaptive approach by tracking the write rate of applications.  If the write rate is high, dirty pages are skipped less often, and vice versa.

\subsubsection{Zero-Page Sharing}
Another technique that can reduce the amount of write-backs is page sharing.  If the Linux VM system can detect that several pages share the same content, it only needs to write one copy to the swap device!  However, tracking page identities or content-based page sharing is not a trivial task.  In our modifications, we implement an extremely limited form of page-sharing through detecting and sharing zero pages.  For workloads like memcached, which reserve significant amounts of memory that may or may not be used, zero pages can account for a decent portion of paging requests. By intercepting swap-in and swap-out requests for zero-pages, we can both reduce the number of write-backs and the memory allocated to zero pages.


\section{Evaluation}
\label{sec:eval}

\noindent 

\begin{verbatim}
in progress
\end{verbatim}

\section{Related Work}
\label{relatedwork}
\noindent Much of the existing work that has been done with Flash memory is relatively recent, and largely focuses on the different tradeoffs that using Flash introduces.  Simply, flash memory does well with random reads, but suffers with random writes.  Even flipping a single bit requires erasing a block of flash and rewriting it.  As such, the core of much research in using flash memory deals with adapting existing approaches to better fit this performance profile.

One problem with flash memory that is addressed in the FlashVM is the dropping of the erasure limit per flash-block over time.  A typical flash block can handle between 10,000 and 100,000 erase cycles before it can’t reliably store data anymore.  FlashVM implements techniques such as page sampling and page sharing in order to reduce the number of writes and prolong the life of the flash device used for swapping.

One of the ways in which FASS attempts to prevent unnecessary writes is by not overwriting pages as is done on disk systems.  In the conventional system, a dirty page is swapped out to the same page slot if the page still has an association with the previously allocated slot.  FASS, however, assigns a new empty page slot whenever a dirty page is swapped out in order to avoid overwriting the previous page slot.

Also of note are papers that have looked deeper into flash storage, either at the flash translation layer (FTL), or making changes to how the write buffer on an SSD is managed (BPLRU, FAB).  There are all sorts of fancy tricks that can be played at this level.  For example, the Block Padding LRU scheme proposed by authors at Samsung has 3 parts to buffer management: block-level LRU lists, page-length padding, and built-in LRU compensation.  The details of these mechanisms are less important than the recognition that significant effort is being expended behind the straightforward SSD interface most programmers will interact with.  Since we dealt primarily with flash cards, we avoided interacting with the more complicated FTL considerations of an SSD.  However, some of the same techniques could be applicable to accessing flash cards (eg. an extra layer of abstraction provided via an API).

Another interesting area is examining the power considerations of using Flash memory.  Park et al. have looked at using Flash as a backing store for demand paging as a way to reduce the power used, perhaps by an embedded system.  They found that by moving pages out of RAM into a demand-paged flash memory, a 30\% reduction in power could be realized at only a 10\% increase in total execution time.  Similarly, Andersen has been developing a power-efficient key-value store system (FAWN) that specifically targets Flash in the form of SSDs.



% -------------------------------------------------------------------------
%                                Conclusion
% -------------------------------------------------------------------------



\section{Conclusions}
\label{sec:conclusion}

\noindent We believe that the changes we have made to the Linux kernel version 3.2.27 will improve the performance of systems such as the Raspberry Pi that use flash based memory. We have reduced the number of writes to flash by porting Swift and Saxena’s FlashVM and prefetching a more accurate amount of pages. By reducing the numbers of writes and more accurately predicting the amount of pages to prefetch, we believe we have improved the performance and the lifetime of flash memory.  We are currently still hopeful to see a decrease in the number of writes after our new prefetching system has been put into effect.

\end{sloppypar}


% -------------------------------------------------------------------------
%                             End Stuff
% -------------------------------------------------------------------------

\setlength{\baselineskip}{12pt}



\end{document}


